package quicksort;

import java.util.Stack;

/**
 * @ClassName quickSort
 * @Description 快排
 * @Author ZJX
 * @Date 2024/9/9 15:39
 * @Version 1.0
 */

public class quickSorting {
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = array[start];
        int i = start;
        int j = end;

        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            while (i < j && array[i] <= pivot) {
                i++;
            }
            swap(array, i, j);
        }

        // 最后把 pivot 放到正确的位置，即 i 和 j 相遇的位置
        swap(array, start, i);

        quick(array, start, i - 1);
        quick(array, i + 1, end);

    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    //   三数取中法通过选择数组开头、中间和结尾三个位置的元素进行比较，取其中的中间值（即中位数）作为枢轴。
    //   这种方法减少了选取最小值或最大值作为枢轴的概率，从而提升了算法的效率。
    public static void quickSortThreeMedian(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        // 选择三数取中的枢轴，并将其放在起始位置
        int pivotIndex = medianOfThree(array, start, end); // 只是代表着索引位置
        swap(array, start, pivotIndex); // 将枢轴放在 start 位置
        int pivot = array[start];  // 将枢轴值存储下来

        int i = start;
        int j = end;

        // 分区过程
        while (i < j) {
            // 从右侧开始，找到第一个比 pivot 小的元素
            while (i < j && array[j] >= pivot) {
                j--;
            }
            // 从左侧开始，找到第一个比 pivot 大的元素
            while (i < j && array[i] <= pivot) {
                i++;
            }
            // 交换 i 和 j 指向的元素
            if (i < j) {
                swap(array, i, j);
            }
        }
        // 将枢轴放回正确的位置
        swap(array, start, i);

        // 递归处理左侧和右侧的子数组
        quickSortThreeMedian(array, start, i - 1);
        quickSortThreeMedian(array, i + 1, end);
    }

    // 三数取中法，选择 start, middle, end 三个位置中的中位数
    private static int medianOfThree(int[] array, int start, int end) {
        int mid = start + (end - start) / 2;
        if (array[start] > array[mid]) {
            swap(array, start, mid);
        }
        if (array[start] > array[end]) {
            swap(array, start, end);
        }
        if (array[mid] > array[end]) {
            swap(array, mid, end);
        }
        return mid; // 返回中位数的索引
    }

    //    挖坑快排法
    public static void pitFillQuickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = array[start];
        int left = start;
        int right = end;


        while (left < right) {
            while (left < right && array[right] >= pivot) {
                right--;
            }

            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;

        pitFillQuickSort(array, start, left - 1);
        pitFillQuickSort(array, left + 1, end);
    }

    public static void nonRecursiveQuickSort(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        int pivot = partition(arr, start, end);

    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];  // 选择第一个元素作为基准
        int i = low + 1;
        int j = high;

        while (i <= j) {
            // 找到左边第一个比基准大的元素
            while (i <= j && arr[i] <= pivot) {
                i++;
            }
            // 找到右边第一个比基准小的元素
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            // 交换左边的大的元素和右边的较小元素
            if (i < j) {
                swap(arr, i, j);
            }
        }

        // 将基准元素放到正确的位置
        swap(arr, low, j);
        return j;  // 返回基准元素的位置
    }


}
